﻿#include <iostream>

static int walkRecur(int M, int N, int x, int y, int remain)
{
    if (x < 0 || y < 0 || x >= M || y >= N) return 0;

    if (remain == 0) return 1;

    return walkRecur(M, N, x - 1, y, remain - 1) +
        walkRecur(M, N, x + 1, y, remain - 1) +
        walkRecur(M, N, x, y - 1, remain - 1) +
        walkRecur(M, N, x, y + 1, remain - 1);
}

static int getValue(const int* dp, int M, int N, int x, int y, int remain)
{
    if (x < 0 || y < 0 || x >= M || y >= N) return 0;

    return dp[x + y * M + remain * M * N];
}

static int byStrictTable(int M, int N, int startX, int startY, int stepCount)
{
    int* dp = (int*)malloc(M * N * (stepCount + 1) * sizeof(int));
    memset(dp, 0, M * N * (stepCount + 1) * sizeof(int));

    // dp[remain][y][x] = dp[x + y * M + remain * M * N]
    for (int y = 0; y < N; y++)
    {
        for (int x = 0; x < M; x++)
        {
            dp[x + y * M] = 1;
        }
    }

    for (int remain = 1; remain <= stepCount; remain++)
    {
        for (int y = 0; y < N; y++)
        {
            for (int x = 0; x < M; x++)
            {
                dp[x + y * M + remain * M * N] = getValue(dp, M, N, x - 1, y, remain - 1) + getValue(dp, M, N, x + 1, y, remain - 1) + getValue(dp, M, N, x, y - 1, remain - 1) + getValue(dp, M, N, x, y + 1, remain - 1);
            }
        }
    }

    int res = dp[startX + startY * M + stepCount * M * N];
    free(dp);
    return res;
}

// 给一个N* M的二维格子，有一个小人出生在一个坐标(x, y), (x, y)有可能在N* M范围内，也可能在范围外。
// 小人每回合走一步，可以往上、下、左、右四个方向走，走到N* M范围外，或者刚出生就在范围外，就算死亡。
// 问 : 走K步，小人存活的概率是多少 ?
// 先求解小人走K步存活有多少种可能的走法，然后再除以总的可能性的个数。
int main_WalkInRange()
{
    int M = 10;
    int N = 10;
    int startX = 0;
    int startY = 0;
    int stepCount = 10;
    int methodCount = walkRecur(M, N, startX, startY, stepCount);
    int methodCountByStrictTable = byStrictTable(M, N, startX, startY, stepCount);
    float total = pow(4, stepCount);
    printf("%d,%d\n", methodCount, methodCountByStrictTable);
    printf("%f,%f\n", methodCount / total, methodCountByStrictTable / total);
    return 0;
}